# -*- coding: utf-8 -*-
# author: AZJ
# date: 2024/11/19
# 假如命运扼住了你的咽喉，你就去挠她的咯吱窝
from typing import List
def minimumTotal(self, triangle: List[List[int]]) -> int:
    n = len(triangle)
    dp = [[0 for _ in range(len(triangle[i]))] for i in range(n)]
    if n == 1:
        return triangle[0][0]
    dp[0][0] = triangle[0][0]
    for i in range(1, n):
        for j in range(len(dp[i])):
            if j == len(dp[i]) - 1:
                dp[i][j] = dp[i - 1][j - 1] + triangle[i][j]
                continue
            if j == 0:
                dp[i][j] = dp[i - 1][j] + triangle[i][j]
                continue
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j]
    return min(dp[n - 1])